package 剑指offer;

import java.util.Arrays;

import org.junit.Test;

public class _40最小的k个数 {
	@Test
	public void  test() {
		int []arr = {7,8,9,10,1,7};
		quickSort(arr, 0, arr.length-1);
		System.out.println(Arrays.toString(arr));
	}
    public int[] getLeastNumbers(int[] arr, int k) {
    	quickSort(arr, 0, arr.length-1);	
		return Arrays.copyOf(arr, k);

    }
    private void quickSort(int []arr,int l,int r) {
		if(l>=r) return;
		int i=l,j=r;
		//以l为基准找到
		while (i<j) {
			while(i<j&&arr[i] <= arr[r]) i++;
			while(i<j&&arr[j] >= arr[r]) j--;			
			swap(arr, i, j);
		}
		swap(arr, j, r);
		quickSort(arr, l, j-1);//左边
		quickSort(arr, j+1, r);//右边
		
	}
    private void swap(int []arr,int a,int b) {
    	int temp = arr[a];
    	arr[a] = arr[b];
    	arr[b] = temp;
    }
   
    public int[] getLeastNumbers1(int[] arr, int k) {
    	 if (k >= arr.length) return arr;
         return quickSort(arr, k, 0, arr.length - 1);
    }
    private int[] quickSort(int[] arr, int k, int l, int r) {
        int i = l, j = r;
        while (i < j) {
            while (i < j && arr[j] >= arr[l]) j--;
            while (i < j && arr[i] <= arr[l]) i++;
            swap(arr, i, j);
        }
        swap(arr, i, l);
        if (i > k) return quickSort(arr, k, l, i - 1);
        if (i < k) return quickSort(arr, k, i + 1, r);
        return Arrays.copyOf(arr, k);
    }


}
